package 平衡二叉树;

import 相同的树.TreeNode;

class Solution {
    public boolean isBalanced(TreeNode root) {
        //空树也是平衡二叉树
        if(root == null){
            return true;
        }
        //树不是空树,利用方法judge来判断树是否为平衡二叉树
        return judge(root) >= 0;
    }
    //方法judge用来判断平衡二叉树和求树的高度,返回-1代表不是平衡二叉树
    public int judge (TreeNode root){
        //当root为null,此树高度为0
        if(root == null){
            return 0;
        }
        //判断左子树是不是平衡二叉树并求左子树的高度
        int judgeLeft = judge(root.left);
        //返回值小于0,说明左子树不是平衡二叉树,直接返回不用继续判断
        if(judgeLeft <0){
            return -1;
        }
        //判断右子树是不是平衡二叉树并求右子树的高度
        int judgeRight = judge(root.right);
        //Math.abs方法用来求两数差的绝对值,当两树高度差小于1说明是平衡二叉树
        if(judgeLeft>=0 && judgeRight>=0 && Math.abs(judgeLeft - judgeRight)<=1){
            //返回值为树的高度
            return judgeLeft>judgeRight ? (judgeLeft+1) : (judgeRight+1);
        }
        //不满足上述条件说明此树不是平衡二叉树
        return -1;
    }
}